/* -*- Mode: C; indent-tabs-mode: t; c-basic-offset: 4; tab-width: 4 -*- */
/*
 * @brief map-messenger /map-messenger/include/ModUtil.cpp
 * Copyright (C) Matheus Neder, Amanda Duarte, Priscila Cardoso 2010
 * 
 * ModUtil.cpp is free software: you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * ModUtil.cpp is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 * See the GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along
 * with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
/**
 * @brief map-messenger /map-messenger/include/ModUtil.cpp
 * @file ModUtil.cpp
 * @date 05/06/2010
 * @author Matheus Neder <matheusneder@gmail.com>
 * @author Amanda Duarte <mandinhaduarte89@gmail.com>
 * @author Priscila Cardoso <japinha-htinha@hotmail.com>
 */

#include "ModUtil.h"
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <boost/thread.hpp>

extern long iterationModPow;
extern long iterationsGenerateFermatPrime;
extern long iterationsIsFermatPrime;

MapInteger modPow(MapInteger base, MapInteger exponent, MapInteger modulo)
		throw (ModUtilException)
{
	if (base < 0)
	{
		throw ModUtilException("modPow: O argumento base deve "
			"ser maior do que zero");
	}
	if (exponent < 0)
	{
		throw ModUtilException("modPow: O argumento exponent deve "
			"ser maior do que zero");
	}
	if (modulo < 0)
	{
		throw ModUtilException("modPow: O argumento modulo deve "
			"ser maior do que zero");
	}
	MapInteger a = base, p = 1, e = exponent;
	while (e != 0)
	{
		iterationModPow++;
		if ((e % 2) != 0)
		{
			p = (a * p) % modulo;
			e = (e - 1) / 2;
		}
		else
		{
			e = e / 2;
		}
		a = (a * a) % modulo;
	}
	return p;
}

static const int K = 10;

bool isFermatPrime(MapInteger n)
{
	int a;
	for (int i = 0; i < K; i++)
	{
		iterationsIsFermatPrime++;
		a = rand() % (n - 1);
		if (a == 0)
		{
			a = 1;
		}
		try
		{
			if (modPow(a, n - 1, n) != 1)
			{
				return false;
			}
		} catch (...)
		{
			return false;
		}
	}
	return true;
}

//static volatile bool foundFermatPrime = false;

MapInteger generateFermatPrime(MapInteger min)
{
	MapInteger p = MapIntegerUtil::rand(min);
	while (!isFermatPrime(p))
	{
		//		if (foundFermatPrime)
		//			return -1;
		iterationsGenerateFermatPrime++;
		p = MapIntegerUtil::rand(min);
	}
	//	foundFermatPrime = true;
	return p;
}

MapInteger generatePrime(MapInteger min)
{
	return generateFermatPrime(min);
}

//MapInteger generateFermatPrimeSingleThreaded(MapInteger min)
//{
//	foundFermatPrime = false;
//	return generateFermatPrime(min);
//}
//
//void generateFermatPrimeMultiThreadedHelper(MapInteger min, MapInteger* res)
//{
//	//std::cout << generateFermatPrime(min) << std::endl;
//	//srand(time(NULL) + threadid);
//	(*res) = generateFermatPrime(min);
//}
//
//MapInteger generateFermatPrimeMultiThreaded(MapInteger min, int maxThreads)
//{
//	foundFermatPrime = false;
//	boost::thread threads[maxThreads];
//	MapInteger res[maxThreads];
//	MapInteger ret;
//	for (int i = 0; i < maxThreads; i++)
//	{
//		threads[i] = boost::thread(generateFermatPrimeMultiThreadedHelper, min,
//				&(res[i]));
//	}
//	for (int i = 0; i < maxThreads; i++)
//	{
//		threads[i].join();
//	}
//	for (int i = 0; i < maxThreads; i++)
//	{
//		if (res[i] != -1)
//		{
//			ret = res[i];
//			break;
//		}
//	}
//	return ret;
//}
